package club.xiaojiawei.greedy;

/**
 * @author 肖嘉威
 * @version 1.0
 * @date 5/26/22 3:11 PM
 * @question 55. 跳跃游戏
 * @description 给定一个非负整数数组 nums ，你最初位于数组的 第一个下标 。
 * 数组中的每个元素代表你在该位置可以跳跃的最大长度。
 * 判断你是否能够到达最后一个下标。
 */
public class CanJump55 {

    public static void main(String[] args) {
        CanJump55 test = new CanJump55();
        boolean result = test.canJump6(new int[]{3, 2, 1,0, 2, 1});
        System.out.println("能否到达最后一个下标："+result);
    }

    /**
     * 朴素法(超时了)
     * @param nums
     * @return
     */
    public boolean canJump(int[] nums) {
        if (nums.length == 1){
            return true;
        }
        return recursion(nums,0);
    }

    public boolean recursion(int[] nums, int index){
        if (index + 1 >= nums.length){
            return true;
        }
        int step = nums[index];
        for (int i = 1; i <= step; i++) {
            if (recursion(nums, index + i)){
                return true;
            }
        }
        return false;
    }

    /**
     * 找0逆向遍历
     * 找到值为0的地方，然后从0的前一个元素往前遍历判断是否能跳过这个0,如果不能则返回false
     * @param nums
     * @return
     */
    public boolean canJump2(int[] nums) {
        int length = nums.length - 1;
        boolean flag;
        for (int i = 0; i < length;) {
            if (nums[i] == 0){
                flag = true;
                for (int j = i - 1; j >= 0; j--){
                    if (nums[j] + j > i) {
                        flag = false;
                        i = nums[j] + j;
                        break;
                    }
                }
                if (flag){
                    return false;
                }
            }else {
                i++;
            }
        }
        return true;
    }

    /**
     * 民间-逆向遍历
     * 从后往前遍历盘算前一个元素能否到达当前元素
     * @param nums
     * @return
     */
    public boolean canJump4(int[] nums) {
        int length = nums.length;
        if (length == 1) {
            return true;
        }
        int target = length - 1;
        int cur = length - 2;
        while (cur >= 0) {
            if (nums[cur] >= (target - cur)) {
                target = cur;
            }
            cur--;
        }
        return target == 0;
    }

    /**
     * 官方-dp
     * 用数组记录能否到达该位置
     * @param nums
     * @return
     */
    public boolean canJump5(int[] nums) {
        boolean[] dp = new boolean[nums.length];
        dp[0] = true;
        for (int i = 1; i < nums.length; i++) {
            for (int j = 0; j < i; j++) {
                if (dp[j] && nums[j] + j >= i) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[nums.length - 1];
    }

    /**
     * 官方-贪心
     * 以最远跳跃距离作为遍历的终止值，且遍历时不断更新最远跳跃距离
     * @param nums
     * @return
     */
    public boolean canJump6(int[] nums) {
        if (nums.length == 1) {
            return true;
        }
        int cover = nums[0];
        for (int i = 0; i <= cover; i++) {
            cover = Math.max(cover, i + nums[i]);
            if (cover >= nums.length - 1) {
                return true;
            }
        }
        return false;
    }
}
